LeetCode 75 Level 1 - Day 3 Linked List

21. Merge Two Sorted Lists

• 題目連結
• 難易度：Easy

題目敘述

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

預設函數

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

}

題目輸入限制

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

解題過程及程式碼

本題是給2個linked list，資料都是放著由小到大的整數 (範圍是-100到100)，我們要回傳1個linked list的head，內容是2個linked list的全部節點依資料的小到大排列，例如圖Fig. 1，Input: list1 = [1,2,4], list2 = [1,3,4]，Output: [1,1,2,3,4,4]，若是資料大小相同則先後順序並無所謂。

我們先來複習linked List這個資料結構，linked List是一個由結構組合成的資料型態，由一個一個的結構串接而成，如下圖Fig. 2所示，一個一個結構稱為節點，內容主要有兩部分，一部分儲存節點所帶有的資料，另一部分就是儲存下一個節點的指標，白話就是記錄下一個節點在電腦裡的位置，如此一來我們就可以從第一個節點依序查詢完所有的節點，找到我們想要的資料。

• 題目已經幫我們預設好了叫做ListNode的結構，裡面有1個int型態的整數，還有1個指向ListNode這種結構型態的指標

  struct ListNode {
      int val;
      struct ListNode *next;
  };
  

• 建立節點的方法

  /* 宣告1個指向ListNode這種結構型態的指標 */
  struct ListNode *head;
  /* 向系統要一個ListNode這種結構型態大小的空間，然後讓指標指向它 */
  head = (struct ListNode*)malloc(sizeof(struct ListNode));
  

• 新增節點：把一個節點接到另一個節點的後面，也可以加入對next指標是否為空的判斷

  void appendList(struct ListNode* list1, struct ListNode* list2) {
      list1->next = list2;
  }
  

想法是將2個list最開頭節點元素做比較，將較小數值的節點取出來做新的list，被取出的list頭一個節點拿掉，再繼續比較2個list最開頭的節點，再將數值較小的取出，接著循環下去，最後執行到題目2個list都取完，如下圖Fig. 3所示

• 程式碼

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *head, *head_temp;
    struct ListNode* list1_new_head = list1;  // 用來記錄list1的新開頭節點
    struct ListNode* list2_new_head = list2;  // 用來記錄list2的新開頭節點

    /* 宣告head作為題目的Output指標 */
    head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    head_temp = head;

    /* 前面先處理題目如果有空節點 */
    if ((list1 == NULL) && (list2 == NULL)) {
        return NULL;
    } else if (list1 == NULL) {
        head->val = list2->val;
        list2_new_head = list2_new_head->next;
    } else if (list2 == NULL) {
        head->val = list1->val;
        list1_new_head = list1_new_head->next;
    /* 判斷頭節點的大小 */
    } else if (list1_new_head->val <= list2_new_head->val) {
        head->val = list1_new_head->val;
        list1_new_head = list1_new_head->next;
    } else {        
        head->val = list2_new_head->val;
        list2_new_head = list2_new_head->next;
    }

    while ((list1_new_head != NULL) || (list2_new_head != NULL)) {  /* 執行至2個list都取完 */
        /* 如果list1先取完則直接取list2的節點 */
        if (list1_new_head == NULL) {
            appendList(head_temp, list2_new_head);
            head_temp = head_temp->next;
            list2_new_head = list2_new_head->next;
            continue;
        /* 如果list2先取完則直接取list1的節點 */
        } else if (list2_new_head == NULL) {
            appendList(head_temp, list1_new_head);
            head_temp = head_temp->next;
            list1_new_head = list1_new_head->next;
            continue;
        } else if (list1_new_head->val <= list2_new_head->val) {
            appendList(head_temp, list1_new_head);
            head_temp = head_temp->next;
            list1_new_head = list1_new_head->next;
        } else {        
            appendList(head_temp, list2_new_head);
            head_temp = head_temp->next;
            list2_new_head = list2_new_head->next;
        }
    }
    return head;
}

void appendList(struct ListNode* list1, struct ListNode* list2) {
    list1->next = list2;
}

今天就到這裡，謝謝大家!